package code;

public class Code222 {
	
	public int leftHigh(TreeNode p){
		int cnt=0;
		while(p!=null){
			cnt++;
			p=p.left;
		}
		return cnt;
	}
	
	public int rightHigh(TreeNode p){
		int cnt=0;
		while(p!=null){
			cnt++;
			p=p.right;
		}
		return cnt;
	}
	
	/*
	 * 递归思想，如果左子树的高度lh=右子树的高度rh，则node=（1<<lh）-1
	 * 否则node=countLeft(p.left)+countRight(p.right)+1;
	 */
    public int countNodes(TreeNode root) {
    	if(root==null)
    		return 0;
    	int lh=leftHigh(root.left);
    	int rh=rightHigh(root.right);
    	if(lh==rh)
    		return (1<<lh)-1;
    	else{
    		return countNodes(root.left)+countNodes(root.right)+1;
    	}
    }
    
    public static void main(String[] args){
    	
    }
}
